In recent years, various types of cracking methods have been devised which analyze an encryption key using secondary information that is generated when an encryption module provided in hardware or software performs encryption. For example, in a cracking method known as a timing attack, the analysis of an encryption key is performed making use of the fact that the time required by the encryption module for encryption is different, although only slightly, depending on the value of the encryption key used in the encryption. More specifically, in a timing attack, the encryption key is cracked by using secondary information which indicates the processing time during encryption. Among such cracking methods, various cracking methods such as “Simple Power Analysis” and “Differential Power Analysis” have been devised as methods for cracking the encryption key using the power consumption during encryption as secondary information. It is reported that, in recent years, partly due to the low cost at which high-performance measurement devices have become available, it is possible for such cracking methods to analyze actual goods that are provided with encryption such as an IC (Integrated Circuit) card. In addition, numerous methods have been devised, such as cracking methods that use the intensity of electromagnetic waves emitted from an encryption module during encryption as secondary information. In the following description, cracking methods, which analyze an encryption key using the power consumption of an encryption module during encryption as a lead, shall be referred to generally as “power analysis attacks”. Although the present invention below will be described using the power analysis attack as an example, the present invention can also be described in the same manner for other cracking methods which make use of secondary information. In other words, the present invention can be applied not only to power analysis attacks, but also to cracking methods which perform key extrapolation using secondary information generated from an encryption module during encryption.
An overview of the power analysis attack shall be described. Below, the present invention shall be described based on an example in which a power analysis attack is applied to AES (Advanced Encryption Standard) cryptography (refer to patent document 1 for details of AES cryptography). FIG. 1 is a block diagram for explaining an overview of AES cryptography process. Although AES cryptography supports three types of key sizes, namely the 128-bit, 192-bit, and 256-bit sizes, the present invention is described below for a key size of 128-bits. Furthermore, although in AES cryptography, 128-bit×11 key pieces, known as round keys K0, K1, . . . K10 are generated based on the 128-bit round key; here, the present invention is described under the assumption that the round keys are already generated. FIG. 1 does not show the round key generation process.
(AES Cryptography Process Overview)
An overview of the encryption in AES cryptography shall be described.
The AES encryption process performs an exclusive OR operation 10a, a table transformation process (S) 10b and a linear transformation (L1) 10c bit-wise with the round key K0 on the 128-bit plain text P. Next, the same process series above is performed using the round key K1 (11a through 11c). Further, the same process series is performed in sequence using the round keys K2, K3, . . . K9. However, for the process series using the round key K9, a linear transformation L2 is performed instead of the linear transformation L1 (19c). Finally, a bitwise exclusive OR operation is performed with the round key K10(19d), and the resulting value is a ciphertext C.
(Table Transformation S (10b))
The processes in the table transformation 10b are described below. Note that the table transformations 11b, 12b, . . . 19b are identical to the table transformation 10b. 
FIG. 2 is a block diagram which shows the processes of the table transformation 10b. The 128-bit inputted data is divided from the most significant bit into 8-bit units, resulting in 16 8-bit pieces. Subsequently, a table transformation process is performed for each 8-bit data piece by using the transformation table Tab (100a through 100p). Thus the transformation table Tab is a table which shows the relationship between inputted 8-bit units and outputted 8-bit units, and is expressed more specifically by an array Tab[256] of 256 8-bit elements and when inputted 8 bit units are X, the output value Y after the table transformation is obtained with Y=Tab[X].
More specifically, the transformation table used in AES encryption is a table made up of Tab[256]={63h, 7Ch, 77h, 7Bh . . . BBh, 16h}. Here, the “h” in 63h indicates that the “63” is in hexadecimal notation. Here, the output of a table transformation with respect to an input 03h is Tab[2]=77h and the output of the table transformation with respect to the input FEh (decimal number, 254) becomes Tab[254]=BBh. In this way, table transformation processes are performed on each 8-bit data unit. Subsequently, each output result is concatenated in the same order in which the output results were divided, becomes 128-bit and the output data Y becomes 128-bit.
(Linear Transformation L1(10c))
The process for the linear transformation L1 (10c) is described below. Note that the linear transformation processes 11c, 12c, . . . 18c are the same processes as the linear transformation L1.
The linear transformation L1 performs a byte transposition called ShiftRow and a matrix transformation called Mix Column in the following order. First, the input data is divided into 8-bit units A0, A1, . . . A14 and A15. The Shift Row byte transposition re-aligns A0 through A15 and produces 128-bit data. More specifically, data is concatenated in the order from the most significant bit: A0, A5, A10, A15, A4, A9, A14, A3, A8, A13, A2, A7, A12, A1, A6, A11 into 128-bit data.
Subsequently, a MixColumn process is performed on the result of the ShiftRow process above. In other words, the results of the ShiftRow are again divided from the most significant bit into 8-bit units B0, B1, . . . B14 and B15. Next, a matrix operation is performed according to an equation 1 below, with X0=B0, X1=B4, X2=B8, X3=B12, calculating Y0, Y1, Y2, Y3 such that C0=Y0, C4=Y1, C8=Y2 and C12=Y3.
                              (                                                                      Y                  ⁢                                                                          ⁢                  0                                                                                                      Y                  ⁢                                                                          ⁢                  1                                                                                                      Y                  ⁢                                                                          ⁢                  2                                                                                                      Y                  ⁢                                                                          ⁢                  3                                                              )                =                              (                                                                                02                    ⁢                    h                                                                                        03                    ⁢                    h                                                                                        01                    ⁢                    h                                                                                        01                    ⁢                    h                                                                                                                    01                    ⁢                    h                                                                                        02                    ⁢                    h                                                                                        03                    ⁢                    h                                                                                        01                    ⁢                    h                                                                                                                    01                    ⁢                    h                                                                                        01                    ⁢                    h                                                                                        02                    ⁢                    h                                                                                        03                    ⁢                    h                                                                                                                    03                    ⁢                    h                                                                                        01                    ⁢                    h                                                                                        01                    ⁢                    h                                                                                        02                    ⁢                    h                                                                        )                    ×                      (                                                                                X                    ⁢                                                                                  ⁢                    0                                                                                                                    X                    ⁢                                                                                  ⁢                    1                                                                                                                    X                    ⁢                                                                                  ⁢                    2                                                                                                                    X                    ⁢                                                                                  ⁢                    3                                                                        )                                              [                  Equation          ⁢                                          ⁢          1                ]            
Here, the addition and multiplication used in the matrix algebra are operations performed on an extension field GF(2^8). Also, “2^8” stands for 2 to the eighth power. Further, the above matrix algebra (the operation shown in equation 1) is performed with X0=B1, X1=B5, X2=B9, X3=B13, calculating Y0, Y1, Y2 and Y3 such that C1=Y0, C5=Y1, C9=Y2 and C13=Y3. In the same way, the matrix algebra (Equation 1) is performed with X0=B2, X1=B6, X2=B10 and X3=B14, calculating Y0, Y1, Y2 and Y3 such that C2=Y0, C6=Y1, C10=Y2 and C14=Y3. Subsequently, the matrix algebra is performed with X0=B3, X1=B7, X2=B11, X3=B15, calculating Y0, Y1, Y2, Y3 such that C3=Y0, C7=Y1, C11=Y2 and C15=Y3. C0, C1, C2, . . . C14 and C15 obtained above, i.e. the 128-bit data concatenated in sequence from the most significant bit, becomes the output data for the MixColumn process, i.e. the output data of the linear transformation L1.
(Linear Transformation L2 (19c))
The linear transformation L2 (19c) is a linear transformation in which the Mix Column process from the linear transformation L1 has been omitted. In other words, the output data is the result of performing a ShiftRow process alone on the input data for L2.
(Structure of Encryption Device 110)
Below, an example structure is described in which AES encryption is provided as an encryption device.
FIG. 3 is a block diagram which shows an example structure in which AES encryption is provided as an encryption device.
The encryption device 110 is a device which encrypts the plain text P and outputs the ciphertext C, and includes a register 110a, an encryption key storage unit 110b, a round key generation unit 110c, a round key storage unit 110d, an exclusive OR unit 110e, a table holding unit 110f, a table transformation unit 110g, a first linear transformation unit 110h and a second linear transformation unit 110i. 
The register 110a is a storage device for storing intermediate data for the encryption process. The encryption key storage unit 110b is a storage unit for storing the encryption key. The round key generation unit 110c is a processing unit for reading out the encryption key from the encryption key storage unit 110b during the encryption process, generating the round keys K0 through K10 and storing the keys in the round key storage unit 110d. The exclusive OR unit 110e is a processing unit which reads out a round key needed from the round key storage unit 110d and performs an exclusive OR operation. The table holding unit 110f is a storage device for storing the transformation table made of 256 8-bit data pieces above as the Tab[256] array. The table transformation unit 110g is a processing unit which reads out the Tab[256] array from the table holding unit 110f and executes a table transformation process. The first linear transformation unit 110h and the second linear transformation unit 110i are processing units which execute the above linear transformation L1 and the linear transformation L2 processes respectively.
Next, the operations in the encryption device 110 are described. When the plain text P is inputted into the encryption device 110, the plain text P is temporarily stored in the register 110a. Next, the exclusive OR unit 110e reads out the data stored in the register 110a, performs an exclusive OR operation on the round key and overwrites and stores the operation result into the register 110a. Next, the table transformation unit 110g reads out data that is stored in the register 110a, performs a table transformation process, and overwrites and stores the transformation result into the register 110a. Subsequently, the first linear transformation unit 110h reads out the data stored in the register 110a, performs the linear transformation L1 process, and overwrites and stores the transformation result into the register 110a. 
Below, the above processes are repeatedly performed according to the processing order for the AES encryption mentioned above. However, for the linear transformation process in the final repetition, the linear transformation L2 process is performed by the second linear transformation unit 110i, instead of the first linear transformation unit 110h, and further, the exclusive OR unit 110e performs an exclusive OR operation on the round key K10 and overwrites and stores the operation result into the register 110a. Subsequently, the encryption device 110 outputs the data stored in the register 110a as the ciphertext C.
(Power Analysis Attack Against the Encryption Device 110)
An outline of the power analysis attack against the encryption device 110 is described below. In the encryption device 110, the data (intermediate data) on which the AES encryption process is being performed is temporarily stored in the register 110a. More specifically, in FIG. 1, after all of the data passed from one block to another block is stored temporarily in the register 110a, processing is performed by the other block.
A power analysis attack focuses on the storing of intermediate data into the register in the encryption process as above. The power consumption level when data is stored in the register will depend on the content of the data stored. For example, the more bits with a value of “1” in the stored data, the greater the power consumed during storage. Also, when overwriting to the register, the greater the number of bits in the register that are inverted (for example, a “0” bit is written over a bit that is stored as a “1” bit), the greater the power consumed during storage. Using these guidelines, the amount of power consumed when storing bits in the register is measured and the data in the register is estimated. Subsequently, an encryption key used for encryption processing is ascertained from the data value estimated. For example, the exclusive OR unit 110e in FIG. 3 can analyze data after the exclusive OR unit 10a process in FIG. 1 is performed, by analyzing the amount of power consumed when the exclusive OR unit 110e in FIG. 3 stores the data in the register 110a. Here the data is D, and assuming that an analyst knows the value of the plain text P, the round key K0 can be found using K0=D(+)P. Here, “(+)” represents an exclusive OR for every bit. For AES encryption, the encryption key can be found by the analysis above since it is known that the round key K0 is identical to the encryption key.
As described above, it is clear that a intermediate value in the encryption process temporarily stored in the register is estimated from the amount of power consumed during encryption and the encryption key will be estimated there from.
(Counter-Measures for Power Analysis Attacks)
A method known as the masking method has been disclosed as a countermeasure for power analysis attacks (see for example, Patent Document 1). In the encryption device 110 shown in FIG. 3, a problem occurs when the intermediate value is analyzed since it is held during encryption temporarily in the register 110a. The masking method is characterized in that the intermediate value in the encryption process is randomized using random numbers before the intermediate value in the encryption process is stored in the register. Thus, even when the data in the register is estimated using power analysis, the actual intermediate value in the encryption process will not be found since the value in the register data are randomized by a random number. Accordingly, the value of the round key cannot be ascertained.
FIG. 4 and FIG. 5 are block diagrams which describe a processing sequence in which the masking method is applied to AES encryption. Before performing the encryption process, 128-bit random numbers R0 through R10 are generated. Subsequently, exclusive OR operations 20a, 20c, 20e, 21b, . . . 29b, 29d and 29h, which utilize the random numbers generated, are added to the original AES encryption as shown in FIG. 4. Here, the exclusive OR operations 21b, . . . 29b are exclusive OR operations on the result of the linear transformation L1 being applied to the random numbers, and the exclusive OR operation 29h is an exclusive OR operation on the result of the linear transformation L2 being applied to the random numbers. Here, the intermediate value T in the encryption process is effected by the random number R0 and randomized by the exclusive OR operation 20a. However, afterwards, the effect is cancelled out when the exclusive OR operation 20c performs an exclusive OR operation on the random number R0. In the same way, since randomizing effects of the random numbers R1, R2, . . . R10 are cancelled out, the ciphertext C which is ultimately obtained is identical to the ciphertext obtained by the original AES encryption process shown in FIG. 1.
When actually implemented as an encryption device, encryption processing is implemented not with the structure in FIG. 4 but with the structure in FIG. 5. The difference between FIG. 4 and FIG. 5 is that the process series in FIG. 4: “Exclusive OR operation on a random number→Table transformation→Exclusive OR operation on a random number” has been replaced with “Table transformation by a randomized transformation table”. Below, this point will be explained.
FIG. 6 is a block diagram for describing the inner structure of the random table transformation 30c in FIG. 5. Note that the random table transformations 31b, 32b . . . 39b are the same as the random table transformation 30c, except for the random numbers used. The 128-bit input data X is divided into 8-bits from the most significant bit, into x0, x1, . . . x15. Also, the random numbers R0 and R1 are divided into 8-bit units from the most significant bit and become respectively R0a, R0b, . . . R0p and R1a, R1b, . . . R1p. First, exclusive OR operations are performed with R0a, R0b, . . . R0p on x0, x1, . . . x15. Next, table transformations using the transformation table Tab in AES encryption are performed respectively on the results (each 8-bit piece). Subsequently, exclusive OR operations with R1a, R1b, . . . R1p are performed on each table transformation result respectively and the results are y0, y1, . . . y15 respectively. y0, y1, . . . y15, i.e. the concatenated 128-bit data in order from the most significant bit, is outputted as Y.
Thus, when the random number R0 (i.e. R0a through R0p) and the random number R1 (i.e. R1a through R1p) are set, the relationship between x0 and y0, the relationship between x1 and y0 and so on up to the relationship between x15 and y15 can be expressed as a transformation table made of 256 pieces of 8-bit data. In other words, the process in FIG. 6 is a process made up of the 16 types of transformation tables Tab0a, Tab0b, . . . Tab0p as well as the table transformation processes 303a, 303b, . . . 303p. 
In summary, the processing sequence in AES encryption for performing counter-measures against masking method cracking is shown in FIG. 5. The processing sequence becomes the following.
(1) Generate 11 128-bit random numbers R0, R1, . . . R10.
(2) Compose a random table transformation Sm0(30c) based on random numbers R0 and R1. More specifically, as shown in FIG. 7, create 16 types of transformation tables that are each made up of 256 pieces of 8-bit data. In the same way, compose the random table transformations Sm1 through Sm9 using the random numbers R1 and R2, R2 and R3, . . . R9 and R10. The specific composition method is the same as Sm0.
(3) Perform an encryption process according to FIG. 5. The present invention differs from the original AES encryption process in the addition of an exclusive OR operation 30a with the random number R0; a linear transformation L2 (39e) of the random number R10; and the addition of an exclusive OR operation 39f on the linear transformation result, and also in that the table transformation processes 30c, 31b, . . . 39b use the randomizing transformation tables created using the random numbers R0 through R10 instead of the original transformation table Tab.    [Non-Patent Document 1] Federal Information Processing Standards Publication 197, “Specification for the ADVANCED ENCRYPTION STANDARD (AES)”, Nov. 26, 2001    [Patent Document 1] U.S. Pat. No. 6,295,606 Specification